#include "btree.h"
#include "index_manager.h"
#include "../memory/memory_manager.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <errno.h>

static const uint32_t DEFAULT_NODE_SIZE = 4096;
static const uint32_t MIN_KEYS_PER_NODE = 4;

static int btree_key_compare_default(const void* key1, size_t key1_size, 
                                   const void* key2, size_t key2_size) {
    size_t min_size = key1_size < key2_size ? key1_size : key2_size;
    int result = memcmp(key1, key2, min_size);
    if (result == 0) {
        if (key1_size < key2_size) return -1;
        if (key1_size > key2_size) return 1;
        return 0;
    }
    return result;
}

btree_index_t* btree_create(memory_manager_t* memory_mgr, uint32_t node_size) {
    if (!memory_mgr) return NULL;
    if (node_size == 0) node_size = DEFAULT_NODE_SIZE;
    
    btree_index_t* btree = mm_alloc(memory_mgr, sizeof(btree_index_t), MEM_TYPE_INDEX_BUFFER);
    if (!btree) return NULL;
    
    memset(btree, 0, sizeof(btree_index_t));
    btree->memory_mgr = memory_mgr;
    btree->node_size = node_size;
    btree->max_entries = (node_size - sizeof(btree_node_t)) / sizeof(btree_entry_t);
    if (btree->max_entries < MIN_KEYS_PER_NODE) {
        btree->max_entries = MIN_KEYS_PER_NODE;
    }
    btree->allow_duplicates = false;
    btree->height = 0;
    btree->total_entries = 0;
    
    if (pthread_rwlock_init(&btree->tree_lock, NULL) != 0) {
        mm_free(memory_mgr, btree);
        return NULL;
    }
    
    btree->root = btree_node_create(memory_mgr, BTREE_NODE_LEAF, btree->max_entries);
    if (!btree->root) {
        pthread_rwlock_destroy(&btree->tree_lock);
        mm_free(memory_mgr, btree);
        return NULL;
    }
    btree->root->is_root = true;
    btree->height = 1;
    
    return btree;
}

void btree_destroy(btree_index_t* btree) {
    if (!btree) return;
    
    pthread_rwlock_wrlock(&btree->tree_lock);
    
    if (btree->root) {
        btree_node_destroy(btree->root);
    }
    
    pthread_rwlock_unlock(&btree->tree_lock);
    pthread_rwlock_destroy(&btree->tree_lock);
    
    mm_free(btree->memory_mgr, btree);
}

btree_node_t* btree_node_create(memory_manager_t* memory_mgr, btree_node_type_t type, 
                               uint32_t max_entries) {
    if (!memory_mgr || max_entries == 0) return NULL;
    
    btree_node_t* node = mm_alloc(memory_mgr, sizeof(btree_node_t), MEM_TYPE_INDEX_BUFFER);
    if (!node) return NULL;
    
    memset(node, 0, sizeof(btree_node_t));
    node->type = type;
    node->is_root = false;
    node->entry_count = 0;
    node->max_entries = max_entries;
    node->memory_mgr = memory_mgr;
    
    node->entries = mm_alloc(memory_mgr, 
                                       sizeof(btree_entry_t) * max_entries, MEM_TYPE_INDEX_BUFFER);
    if (!node->entries) {
        mm_free(memory_mgr, node);
        return NULL;
    }
    memset(node->entries, 0, sizeof(btree_entry_t) * max_entries);
    
    if (pthread_rwlock_init(&node->rwlock, NULL) != 0) {
        mm_free(memory_mgr, node->entries);
        mm_free(memory_mgr, node);
        return NULL;
    }
    
    return node;
}

void btree_node_destroy(btree_node_t* node) {
    if (!node) return;
    
    pthread_rwlock_wrlock(&node->rwlock);
    
    for (uint32_t i = 0; i < node->entry_count; i++) {
        if (node->entries[i].key) {
            mm_free(node->memory_mgr, node->entries[i].key);
        }
        if (node->entries[i].value) {
            mm_free(node->memory_mgr, node->entries[i].value);
        }
        if (node->type == BTREE_NODE_INTERNAL && node->entries[i].child) {
            btree_node_destroy(node->entries[i].child);
        }
    }
    
    if (node->entries) {
        mm_free(node->memory_mgr, node->entries);
    }
    
    pthread_rwlock_unlock(&node->rwlock);
    pthread_rwlock_destroy(&node->rwlock);
    
    mm_free(node->memory_mgr, node);
}

int btree_key_compare(const void* key1, size_t key1_size, const void* key2, size_t key2_size) {
    return btree_key_compare_default(key1, key1_size, key2, key2_size);
}

int btree_find_key_position(btree_node_t* node, const void* key, size_t key_size) {
    if (!node || !key) return -1;
    
    int left = 0;
    int right = (int)node->entry_count - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = btree_key_compare(key, key_size, 
                                  node->entries[mid].key, 
                                  node->entries[mid].key_size);
        
        if (cmp == 0) {
            return mid;
        } else if (cmp < 0) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

static btree_entry_t* btree_create_entry(memory_manager_t* memory_mgr,
                                       const void* key, size_t key_size,
                                       const void* value, size_t value_size) {
    btree_entry_t* entry = mm_alloc(memory_mgr, sizeof(btree_entry_t), MEM_TYPE_INDEX_BUFFER);
    if (!entry) return NULL;
    
    memset(entry, 0, sizeof(btree_entry_t));
    
    entry->key = mm_alloc(memory_mgr, key_size, MEM_TYPE_INDEX_BUFFER);
    if (!entry->key) {
        mm_free(memory_mgr, entry);
        return NULL;
    }
    memcpy(entry->key, key, key_size);
    entry->key_size = key_size;
    
    if (value && value_size > 0) {
        entry->value = mm_alloc(memory_mgr, value_size, MEM_TYPE_INDEX_BUFFER);
        if (!entry->value) {
            mm_free(memory_mgr, entry->key);
            mm_free(memory_mgr, entry);
            return NULL;
        }
        memcpy(entry->value, value, value_size);
        entry->value_size = value_size;
    }
    
    return entry;
}

index_result_t btree_node_insert_entry(btree_node_t* node, btree_entry_t* entry, uint32_t pos) {
    if (!node || !entry || pos > node->entry_count || 
        node->entry_count >= node->max_entries) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_wrlock(&node->rwlock);
    
    for (uint32_t i = node->entry_count; i > pos; i--) {
        node->entries[i] = node->entries[i-1];
    }
    
    node->entries[pos] = *entry;
    node->entry_count++;
    
    pthread_rwlock_unlock(&node->rwlock);
    return INDEX_SUCCESS;
}

index_result_t btree_node_delete_entry(btree_node_t* node, uint32_t pos) {
    if (!node || pos >= node->entry_count) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_wrlock(&node->rwlock);
    
    if (node->entries[pos].key) {
        mm_free(node->memory_mgr, node->entries[pos].key);
    }
    if (node->entries[pos].value) {
        mm_free(node->memory_mgr, node->entries[pos].value);
    }
    
    for (uint32_t i = pos; i < node->entry_count - 1; i++) {
        node->entries[i] = node->entries[i + 1];
    }
    
    memset(&node->entries[node->entry_count - 1], 0, sizeof(btree_entry_t));
    node->entry_count--;
    
    pthread_rwlock_unlock(&node->rwlock);
    return INDEX_SUCCESS;
}

btree_node_t* btree_node_split(btree_node_t* node, btree_entry_t* new_entry) {
    if (!node || !new_entry) return NULL;
    
    uint32_t mid = node->max_entries / 2;
    btree_node_t* new_node = btree_node_create(node->memory_mgr, node->type, 
                                              node->max_entries);
    if (!new_node) return NULL;
    
    pthread_rwlock_wrlock(&node->rwlock);
    
    for (uint32_t i = mid; i < node->entry_count; i++) {
        new_node->entries[new_node->entry_count++] = node->entries[i];
        memset(&node->entries[i], 0, sizeof(btree_entry_t));
    }
    
    node->entry_count = mid;
    
    if (node->type == BTREE_NODE_LEAF) {
        new_node->next = node->next;
        new_node->prev = node;
        if (node->next) {
            node->next->prev = new_node;
        }
        node->next = new_node;
    }
    
    new_node->parent = node->parent;
    
    pthread_rwlock_unlock(&node->rwlock);
    
    return new_node;
}

index_result_t btree_node_merge(btree_node_t* left, btree_node_t* right) {
    if (!left || !right || left->type != right->type) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    if (left->entry_count + right->entry_count > left->max_entries) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_wrlock(&left->rwlock);
    pthread_rwlock_wrlock(&right->rwlock);
    
    for (uint32_t i = 0; i < right->entry_count; i++) {
        left->entries[left->entry_count + i] = right->entries[i];
        memset(&right->entries[i], 0, sizeof(btree_entry_t));
    }
    
    left->entry_count += right->entry_count;
    right->entry_count = 0;
    
    if (left->type == BTREE_NODE_LEAF) {
        left->next = right->next;
        if (right->next) {
            right->next->prev = left;
        }
    }
    
    pthread_rwlock_unlock(&right->rwlock);
    pthread_rwlock_unlock(&left->rwlock);
    
    return INDEX_SUCCESS;
}

static btree_node_t* btree_find_leaf(btree_index_t* btree, const void* key, size_t key_size) {
    btree_node_t* current = btree->root;
    
    while (current && current->type == BTREE_NODE_INTERNAL) {
        pthread_rwlock_rdlock(&current->rwlock);
        
        int pos = btree_find_key_position(current, key, key_size);
        if (pos >= (int)current->entry_count) {
            pos = current->entry_count - 1;
        }
        
        btree_node_t* next = current->entries[pos].child;
        pthread_rwlock_unlock(&current->rwlock);
        current = next;
    }
    
    return current;
}

index_result_t btree_insert(btree_index_t* btree, const void* key, size_t key_size,
                           const void* value, size_t value_size) {
    if (!btree || !key || key_size == 0) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_wrlock(&btree->tree_lock);
    
    btree->inserts++;
    
    btree_node_t* leaf = btree_find_leaf(btree, key, key_size);
    if (!leaf) {
        pthread_rwlock_unlock(&btree->tree_lock);
        return INDEX_ERROR_OUT_OF_MEMORY;
    }
    
    pthread_rwlock_wrlock(&leaf->rwlock);
    
    int pos = btree_find_key_position(leaf, key, key_size);
    
    if (pos < (int)leaf->entry_count &&
        btree_key_compare(key, key_size, 
                         leaf->entries[pos].key, 
                         leaf->entries[pos].key_size) == 0) {
        if (!btree->allow_duplicates) {
            pthread_rwlock_unlock(&leaf->rwlock);
            pthread_rwlock_unlock(&btree->tree_lock);
            return INDEX_ERROR_KEY_EXISTS;
        }
    }
    
    btree_entry_t* new_entry = btree_create_entry(btree->memory_mgr, 
                                                key, key_size, value, value_size);
    if (!new_entry) {
        pthread_rwlock_unlock(&leaf->rwlock);
        pthread_rwlock_unlock(&btree->tree_lock);
        return INDEX_ERROR_OUT_OF_MEMORY;
    }
    
    if (leaf->entry_count < leaf->max_entries) {
        index_result_t result = btree_node_insert_entry(leaf, new_entry, pos);
        mm_free(btree->memory_mgr, new_entry);
        
        if (result == INDEX_SUCCESS) {
            btree->total_entries++;
        }
        
        pthread_rwlock_unlock(&leaf->rwlock);
        pthread_rwlock_unlock(&btree->tree_lock);
        return result;
    }
    
    btree_node_t* new_leaf = btree_node_split(leaf, new_entry);
    if (!new_leaf) {
        mm_free(btree->memory_mgr, new_entry->key);
        if (new_entry->value) {
            mm_free(btree->memory_mgr, new_entry->value);
        }
        mm_free(btree->memory_mgr, new_entry);
        pthread_rwlock_unlock(&leaf->rwlock);
        pthread_rwlock_unlock(&btree->tree_lock);
        return INDEX_ERROR_OUT_OF_MEMORY;
    }
    
    btree->splits++;
    
    if (pos < (int)(leaf->max_entries / 2)) {
        btree_node_insert_entry(leaf, new_entry, pos);
    } else {
        btree_node_insert_entry(new_leaf, new_entry, 
                               pos - (leaf->max_entries / 2));
    }
    
    mm_free(btree->memory_mgr, new_entry);
    
    if (leaf->is_root) {
        btree_node_t* new_root = btree_node_create(btree->memory_mgr, 
                                                  BTREE_NODE_INTERNAL,
                                                  btree->max_entries);
        if (!new_root) {
            pthread_rwlock_unlock(&leaf->rwlock);
            pthread_rwlock_unlock(&btree->tree_lock);
            return INDEX_ERROR_OUT_OF_MEMORY;
        }
        
        new_root->is_root = true;
        leaf->is_root = false;
        new_leaf->parent = new_root;
        leaf->parent = new_root;
        
        btree_entry_t root_entry;
        memset(&root_entry, 0, sizeof(btree_entry_t));
        root_entry.key = mm_alloc(btree->memory_mgr, 
                                            new_leaf->entries[0].key_size, MEM_TYPE_INDEX_BUFFER);
        if (!root_entry.key) {
            btree_node_destroy(new_root);
            pthread_rwlock_unlock(&leaf->rwlock);
            pthread_rwlock_unlock(&btree->tree_lock);
            return INDEX_ERROR_OUT_OF_MEMORY;
        }
        
        memcpy(root_entry.key, new_leaf->entries[0].key, 
               new_leaf->entries[0].key_size);
        root_entry.key_size = new_leaf->entries[0].key_size;
        root_entry.child = new_leaf;
        
        new_root->entries[0].child = leaf;
        new_root->entries[1] = root_entry;
        new_root->entry_count = 2;
        
        btree->root = new_root;
        btree->height++;
    }
    
    btree->total_entries++;
    
    pthread_rwlock_unlock(&leaf->rwlock);
    pthread_rwlock_unlock(&btree->tree_lock);
    
    return INDEX_SUCCESS;
}

index_result_t btree_search(btree_index_t* btree, const void* key, size_t key_size,
                           index_search_result_t* result) {
    if (!btree || !key || key_size == 0 || !result) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_rdlock(&btree->tree_lock);
    
    btree->searches++;
    
    btree_node_t* leaf = btree_find_leaf(btree, key, key_size);
    if (!leaf) {
        pthread_rwlock_unlock(&btree->tree_lock);
        return INDEX_ERROR_KEY_NOT_FOUND;
    }
    
    pthread_rwlock_rdlock(&leaf->rwlock);
    
    int pos = btree_find_key_position(leaf, key, key_size);
    
    if (pos < (int)leaf->entry_count &&
        btree_key_compare(key, key_size,
                         leaf->entries[pos].key,
                         leaf->entries[pos].key_size) == 0) {
        
        result->found = true;
        result->value = leaf->entries[pos].value;
        result->value_size = leaf->entries[pos].value_size;
        result->record_id = 0;
        
        pthread_rwlock_unlock(&leaf->rwlock);
        pthread_rwlock_unlock(&btree->tree_lock);
        return INDEX_SUCCESS;
    }
    
    result->found = false;
    result->value = NULL;
    result->value_size = 0;
    result->record_id = 0;
    
    pthread_rwlock_unlock(&leaf->rwlock);
    pthread_rwlock_unlock(&btree->tree_lock);
    
    return INDEX_ERROR_KEY_NOT_FOUND;
}

index_result_t btree_delete(btree_index_t* btree, const void* key, size_t key_size) {
    if (!btree || !key || key_size == 0) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_wrlock(&btree->tree_lock);
    
    btree->deletes++;
    
    btree_node_t* leaf = btree_find_leaf(btree, key, key_size);
    if (!leaf) {
        pthread_rwlock_unlock(&btree->tree_lock);
        return INDEX_ERROR_KEY_NOT_FOUND;
    }
    
    pthread_rwlock_wrlock(&leaf->rwlock);
    
    int pos = btree_find_key_position(leaf, key, key_size);
    
    if (pos >= (int)leaf->entry_count ||
        btree_key_compare(key, key_size,
                         leaf->entries[pos].key,
                         leaf->entries[pos].key_size) != 0) {
        pthread_rwlock_unlock(&leaf->rwlock);
        pthread_rwlock_unlock(&btree->tree_lock);
        return INDEX_ERROR_KEY_NOT_FOUND;
    }
    
    index_result_t result = btree_node_delete_entry(leaf, pos);
    
    if (result == INDEX_SUCCESS) {
        btree->total_entries--;
    }
    
    pthread_rwlock_unlock(&leaf->rwlock);
    pthread_rwlock_unlock(&btree->tree_lock);
    
    return result;
}

index_result_t btree_update(btree_index_t* btree, const void* key, size_t key_size,
                           const void* value, size_t value_size) {
    if (!btree || !key || key_size == 0) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_wrlock(&btree->tree_lock);
    
    btree_node_t* leaf = btree_find_leaf(btree, key, key_size);
    if (!leaf) {
        pthread_rwlock_unlock(&btree->tree_lock);
        return INDEX_ERROR_KEY_NOT_FOUND;
    }
    
    pthread_rwlock_wrlock(&leaf->rwlock);
    
    int pos = btree_find_key_position(leaf, key, key_size);
    
    if (pos >= (int)leaf->entry_count ||
        btree_key_compare(key, key_size,
                         leaf->entries[pos].key,
                         leaf->entries[pos].key_size) != 0) {
        pthread_rwlock_unlock(&leaf->rwlock);
        pthread_rwlock_unlock(&btree->tree_lock);
        return INDEX_ERROR_KEY_NOT_FOUND;
    }
    
    if (leaf->entries[pos].value) {
        mm_free(btree->memory_mgr, leaf->entries[pos].value);
        leaf->entries[pos].value = NULL;
        leaf->entries[pos].value_size = 0;
    }
    
    if (value && value_size > 0) {
        leaf->entries[pos].value = mm_alloc(btree->memory_mgr, value_size, MEM_TYPE_INDEX_BUFFER);
        if (!leaf->entries[pos].value) {
            pthread_rwlock_unlock(&leaf->rwlock);
            pthread_rwlock_unlock(&btree->tree_lock);
            return INDEX_ERROR_OUT_OF_MEMORY;
        }
        memcpy(leaf->entries[pos].value, value, value_size);
        leaf->entries[pos].value_size = value_size;
    }
    
    pthread_rwlock_unlock(&leaf->rwlock);
    pthread_rwlock_unlock(&btree->tree_lock);
    
    return INDEX_SUCCESS;
}

btree_iterator_t* btree_range_scan(btree_index_t* btree,
                                  const void* start_key, size_t start_key_size,
                                  const void* end_key, size_t end_key_size,
                                  bool forward) {
    if (!btree) return NULL;
    
    btree_iterator_t* iter = mm_alloc(btree->memory_mgr, 
                                                 sizeof(btree_iterator_t), MEM_TYPE_INDEX_BUFFER);
    if (!iter) return NULL;
    
    memset(iter, 0, sizeof(btree_iterator_t));
    iter->index = btree;
    iter->forward = forward;
    iter->is_valid = false;
    
    if (start_key && start_key_size > 0) {
        iter->start_key = mm_alloc(btree->memory_mgr, start_key_size, MEM_TYPE_INDEX_BUFFER);
        if (!iter->start_key) {
            mm_free(btree->memory_mgr, iter);
            return NULL;
        }
        memcpy(iter->start_key, start_key, start_key_size);
        iter->start_key_size = start_key_size;
        
        iter->current_node = btree_find_leaf(btree, start_key, start_key_size);
        if (iter->current_node) {
            iter->current_entry = btree_find_key_position(iter->current_node, 
                                                        start_key, start_key_size);
            iter->is_valid = true;
        }
    } else {
        btree_node_t* node = btree->root;
        while (node && node->type == BTREE_NODE_INTERNAL) {
            node = node->entries[0].child;
        }
        iter->current_node = node;
        iter->current_entry = 0;
        iter->is_valid = (node && node->entry_count > 0);
    }
    
    if (end_key && end_key_size > 0) {
        iter->end_key = mm_alloc(btree->memory_mgr, end_key_size, MEM_TYPE_INDEX_BUFFER);
        if (!iter->end_key) {
            if (iter->start_key) {
                mm_free(btree->memory_mgr, iter->start_key);
            }
            mm_free(btree->memory_mgr, iter);
            return NULL;
        }
        memcpy(iter->end_key, end_key, end_key_size);
        iter->end_key_size = end_key_size;
    }
    
    return iter;
}

bool btree_iterator_valid(btree_iterator_t* iter) {
    return iter && iter->is_valid && iter->current_node &&
           iter->current_entry < iter->current_node->entry_count;
}

index_result_t btree_iterator_next(btree_iterator_t* iter) {
    if (!iter || !iter->is_valid) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    if (iter->forward) {
        iter->current_entry++;
        
        if (iter->current_entry >= iter->current_node->entry_count) {
            iter->current_node = iter->current_node->next;
            iter->current_entry = 0;
        }
        
        if (!iter->current_node || iter->current_node->entry_count == 0) {
            iter->is_valid = false;
            return INDEX_SUCCESS;
        }
        
        if (iter->end_key && iter->end_key_size > 0) {
            int cmp = btree_key_compare(
                iter->current_node->entries[iter->current_entry].key,
                iter->current_node->entries[iter->current_entry].key_size,
                iter->end_key, iter->end_key_size);
            
            if (cmp > 0) {
                iter->is_valid = false;
            }
        }
    } else {
        if (iter->current_entry == 0) {
            iter->current_node = iter->current_node->prev;
            if (iter->current_node) {
                iter->current_entry = iter->current_node->entry_count - 1;
            }
        } else {
            iter->current_entry--;
        }
        
        if (!iter->current_node) {
            iter->is_valid = false;
            return INDEX_SUCCESS;
        }
        
        if (iter->start_key && iter->start_key_size > 0) {
            int cmp = btree_key_compare(
                iter->current_node->entries[iter->current_entry].key,
                iter->current_node->entries[iter->current_entry].key_size,
                iter->start_key, iter->start_key_size);
            
            if (cmp < 0) {
                iter->is_valid = false;
            }
        }
    }
    
    return INDEX_SUCCESS;
}

index_result_t btree_iterator_current(btree_iterator_t* iter,
                                     void** key, size_t* key_size,
                                     void** value, size_t* value_size) {
    if (!iter || !iter->is_valid || !iter->current_node ||
        iter->current_entry >= iter->current_node->entry_count) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    btree_entry_t* entry = &iter->current_node->entries[iter->current_entry];
    
    if (key) *key = entry->key;
    if (key_size) *key_size = entry->key_size;
    if (value) *value = entry->value;
    if (value_size) *value_size = entry->value_size;
    
    return INDEX_SUCCESS;
}

void btree_iterator_destroy(btree_iterator_t* iter) {
    if (!iter) return;
    
    if (iter->start_key) {
        mm_free(iter->index->memory_mgr, iter->start_key);
    }
    if (iter->end_key) {
        mm_free(iter->index->memory_mgr, iter->end_key);
    }
    
    mm_free(iter->index->memory_mgr, iter);
}

index_result_t btree_bulk_insert(btree_index_t* btree,
                                const void** keys, size_t* key_sizes,
                                const void** values, size_t* value_sizes,
                                size_t count) {
    if (!btree || !keys || !key_sizes || count == 0) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    for (size_t i = 0; i < count; i++) {
        const void* value = values ? values[i] : NULL;
        size_t value_size = value_sizes ? value_sizes[i] : 0;
        
        index_result_t result = btree_insert(btree, keys[i], key_sizes[i], 
                                           value, value_size);
        if (result != INDEX_SUCCESS && result != INDEX_ERROR_KEY_EXISTS) {
            return result;
        }
    }
    
    return INDEX_SUCCESS;
}

size_t btree_range_delete(btree_index_t* btree,
                         const void* start_key, size_t start_key_size,
                         const void* end_key, size_t end_key_size) {
    if (!btree) return 0;
    
    btree_iterator_t* iter = btree_range_scan(btree, start_key, start_key_size,
                                             end_key, end_key_size, true);
    if (!iter) return 0;
    
    size_t deleted_count = 0;
    
    while (btree_iterator_valid(iter)) {
        void* key;
        size_t key_size;
        
        if (btree_iterator_current(iter, &key, &key_size, NULL, NULL) == INDEX_SUCCESS) {
            if (btree_delete(btree, key, key_size) == INDEX_SUCCESS) {
                deleted_count++;
            }
        }
        
        btree_iterator_next(iter);
    }
    
    btree_iterator_destroy(iter);
    return deleted_count;
}

index_result_t btree_clear(btree_index_t* btree) {
    if (!btree) return INDEX_ERROR_INVALID_PARAM;
    
    pthread_rwlock_wrlock(&btree->tree_lock);
    
    if (btree->root) {
        btree_node_destroy(btree->root);
    }
    
    btree->root = btree_node_create(btree->memory_mgr, BTREE_NODE_LEAF, 
                                   btree->max_entries);
    if (!btree->root) {
        pthread_rwlock_unlock(&btree->tree_lock);
        return INDEX_ERROR_OUT_OF_MEMORY;
    }
    
    btree->root->is_root = true;
    btree->height = 1;
    btree->total_entries = 0;
    
    pthread_rwlock_unlock(&btree->tree_lock);
    return INDEX_SUCCESS;
}

index_result_t btree_rebuild(btree_index_t* btree) {
    return btree_clear(btree);
}

bool btree_validate(btree_index_t* btree) {
    if (!btree || !btree->root) return false;
    
    pthread_rwlock_rdlock(&btree->tree_lock);
    
    bool valid = btree->root->is_root;
    
    pthread_rwlock_unlock(&btree->tree_lock);
    return valid;
}

void btree_get_stats(btree_index_t* btree, index_stats_t* stats) {
    if (!btree || !stats) return;
    
    pthread_rwlock_rdlock(&btree->tree_lock);
    
    memset(stats, 0, sizeof(index_stats_t));
    stats->total_keys = btree->total_entries;
    stats->searches = btree->searches;
    stats->inserts = btree->inserts;
    stats->deletes = btree->deletes;
    stats->avg_depth = (double)btree->height;
    
    pthread_rwlock_unlock(&btree->tree_lock);
}

void btree_print_tree(btree_index_t* btree) {
    if (!btree || !btree->root) return;
    
    printf("B+ Tree (height=%u, entries=%llu):\n", 
           btree->height, (unsigned long long)btree->total_entries);
    btree_print_node(btree->root, 0);
}

void btree_print_node(btree_node_t* node, int level) {
    if (!node) return;
    
    pthread_rwlock_rdlock(&node->rwlock);
    
    for (int i = 0; i < level; i++) {
        printf("  ");
    }
    
    printf("Node[%s, entries=%u]: ", 
           node->type == BTREE_NODE_LEAF ? "LEAF" : "INTERNAL",
           node->entry_count);
    
    for (uint32_t i = 0; i < node->entry_count; i++) {
        printf("[key=%p] ", node->entries[i].key);
    }
    printf("\n");
    
    if (node->type == BTREE_NODE_INTERNAL) {
        for (uint32_t i = 0; i < node->entry_count; i++) {
            if (node->entries[i].child) {
                btree_print_node(node->entries[i].child, level + 1);
            }
        }
    }
    
    pthread_rwlock_unlock(&node->rwlock);
}

static index_result_t btree_interface_insert(index_instance_t* index,
                                            const void* key, size_t key_size,
                                            const void* value, size_t value_size) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    return btree_insert(btree, key, key_size, value, value_size);
}

static index_result_t btree_interface_delete(index_instance_t* index,
                                            const void* key, size_t key_size) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    return btree_delete(btree, key, key_size);
}

static index_result_t btree_interface_update(index_instance_t* index,
                                            const void* key, size_t key_size,
                                            const void* value, size_t value_size) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    return btree_update(btree, key, key_size, value, value_size);
}

static index_result_t btree_interface_search(index_instance_t* index,
                                            const void* key, size_t key_size,
                                            index_search_result_t* result) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    return btree_search(btree, key, key_size, result);
}

static index_iterator_t* btree_interface_range_scan(index_instance_t* index,
                                                   const void* start_key, size_t start_key_size,
                                                   const void* end_key, size_t end_key_size,
                                                   bool forward) {
    if (!index || !index->index_data) return NULL;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    
    btree_iterator_t* btree_iter = btree_range_scan(btree, start_key, start_key_size,
                                                   end_key, end_key_size, forward);
    if (!btree_iter) return NULL;
    
    index_iterator_t* iter = mm_alloc(btree->memory_mgr, 
                                                 sizeof(index_iterator_t), MEM_TYPE_INDEX_BUFFER);
    if (!iter) {
        btree_iterator_destroy(btree_iter);
        return NULL;
    }
    
    memset(iter, 0, sizeof(index_iterator_t));
    iter->index = index;
    iter->internal_state = btree_iter;
    iter->is_valid = btree_iterator_valid(btree_iter);
    iter->forward = forward;
    
    return iter;
}

static bool btree_interface_iterator_valid(index_iterator_t* iter) {
    if (!iter || !iter->internal_state) return false;
    btree_iterator_t* btree_iter = (btree_iterator_t*)iter->internal_state;
    return btree_iterator_valid(btree_iter);
}

static index_result_t btree_interface_iterator_next(index_iterator_t* iter) {
    if (!iter || !iter->internal_state) return INDEX_ERROR_INVALID_PARAM;
    btree_iterator_t* btree_iter = (btree_iterator_t*)iter->internal_state;
    return btree_iterator_next(btree_iter);
}

static index_result_t btree_interface_iterator_current(index_iterator_t* iter,
                                                      void** key, size_t* key_size,
                                                      void** value, size_t* value_size) {
    if (!iter || !iter->internal_state) return INDEX_ERROR_INVALID_PARAM;
    btree_iterator_t* btree_iter = (btree_iterator_t*)iter->internal_state;
    return btree_iterator_current(btree_iter, key, key_size, value, value_size);
}

static void btree_interface_iterator_destroy(index_iterator_t* iter) {
    if (!iter) return;
    
    if (iter->internal_state) {
        btree_iterator_t* btree_iter = (btree_iterator_t*)iter->internal_state;
        btree_iterator_destroy(btree_iter);
    }
    
    if (iter->index && iter->index->index_data) {
        btree_index_t* btree = (btree_index_t*)iter->index->index_data;
        mm_free(btree->memory_mgr, iter);
    }
}

static index_result_t btree_interface_bulk_insert(index_instance_t* index,
                                                 const void** keys, size_t* key_sizes,
                                                 const void** values, size_t* value_sizes,
                                                 size_t count) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    return btree_bulk_insert(btree, keys, key_sizes, values, value_sizes, count);
}

static size_t btree_interface_range_delete(index_instance_t* index,
                                          const void* start_key, size_t start_key_size,
                                          const void* end_key, size_t end_key_size) {
    if (!index || !index->index_data) return 0;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    return btree_range_delete(btree, start_key, start_key_size, end_key, end_key_size);
}

static index_result_t btree_interface_clear(index_instance_t* index) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    return btree_clear(btree);
}

static index_result_t btree_interface_rebuild(index_instance_t* index) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    return btree_rebuild(btree);
}

static void btree_interface_destroy(index_instance_t* index) {
    if (!index || !index->index_data) return;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    btree_destroy(btree);
    index->index_data = NULL;
}

static void btree_interface_get_stats(index_instance_t* index, index_stats_t* stats) {
    if (!index || !index->index_data || !stats) return;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    btree_get_stats(btree, stats);
}

static bool btree_interface_validate(index_instance_t* index) {
    if (!index || !index->index_data) return false;
    btree_index_t* btree = (btree_index_t*)index->index_data;
    return btree_validate(btree);
}

static index_result_t btree_interface_set_config(index_instance_t* index,
                                                const index_config_t* config) {
    if (!index || !config) return INDEX_ERROR_INVALID_PARAM;
    
    memcpy(&index->config, config, sizeof(index_config_t));
    return INDEX_SUCCESS;
}

static void btree_interface_get_config(index_instance_t* index, index_config_t* config) {
    if (!index || !config) return;
    memcpy(config, &index->config, sizeof(index_config_t));
}

index_interface_t* btree_interface_create(void) {
    index_interface_t* interface = malloc(sizeof(index_interface_t));
    if (!interface) return NULL;
    
    memset(interface, 0, sizeof(index_interface_t));
    
    interface->insert = btree_interface_insert;
    interface->delete = btree_interface_delete;
    interface->update = btree_interface_update;
    interface->search = btree_interface_search;
    interface->range_scan = btree_interface_range_scan;
    interface->iterator_valid = btree_interface_iterator_valid;
    interface->iterator_next = btree_interface_iterator_next;
    interface->iterator_current = btree_interface_iterator_current;
    interface->iterator_destroy = btree_interface_iterator_destroy;
    interface->bulk_insert = btree_interface_bulk_insert;
    interface->range_delete = btree_interface_range_delete;
    interface->clear = btree_interface_clear;
    interface->rebuild = btree_interface_rebuild;
    interface->destroy = btree_interface_destroy;
    interface->get_stats = btree_interface_get_stats;
    interface->validate = btree_interface_validate;
    interface->set_config = btree_interface_set_config;
    interface->get_config = btree_interface_get_config;
    
    return interface;
}